{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number Complement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findComplement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数字的补数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>对整数的二进制表示取反（<code>0</code> 变 <code>1</code> ，<code>1</code> 变 <code>0</code>）后，再转换为十进制表示，可以得到这个整数的补数。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，整数 <code>5</code> 的二进制表示是 <code>\"101\"</code> ，取反后得到 <code>\"010\"</code> ，再转回十进制表示得到补数 <code>2</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个整数 <code>num</code> ，输出它的补数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<ol>\n",
    "</ol>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = 5\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = 1\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>1 的二进制表示为 1（没有前导零位），其补数为 0。所以你需要输出 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= num &lt; 2<sup>31</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注意：</strong>本题与 1009 <a href=\"https://leetcode-cn.com/problems/complement-of-base-10-integer/\">https://leetcode-cn.com/problems/complement-of-base-10-integer/</a> 相同</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-complement](https://leetcode.cn/problems/number-complement/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-complement](https://leetcode.cn/problems/number-complement/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5', '1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        s = list(bin(num)[2:])\n",
    "        t = ['1' for i in range(len(s))]\n",
    "        for i in range(len(s)):\n",
    "            s[i] = str(int(s[i]) ^ int(t[i]))\n",
    "        s = int(''.join(s), 2)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        power = 0\n",
    "        for i in range(0, 32):\n",
    "            if num >= 2**i and num < 2**(i+1):\n",
    "                power = i\n",
    "                break\n",
    "        result = (2**(power+1)) - 1\n",
    "        return num^result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        num = bin(num)[2:] \n",
    "        res = ''\n",
    "        for i in range(len(num)):\n",
    "            if num[i] == '0':res += '1'\n",
    "            else:res += '0'\n",
    "        # print (res,num)\n",
    "        return int(res,2) \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "\n",
    "        while num > 0:\n",
    "            ans = ans + ((num%2==0)<<cur)\n",
    "            cur += 1\n",
    "            num >>= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        ans = 0\n",
    "        re_val = 0\n",
    "\n",
    "        ones = 0\n",
    "        meetzero = False\n",
    "\n",
    "        while num !=0:\n",
    "            if not meetzero:\n",
    "                if num%2 == 0:\n",
    "                    meetzero = True\n",
    "                else:\n",
    "                    ones += 1\n",
    "            ans <<= 1\n",
    "            ans = ans + (num%2==0)\n",
    "            num >>= 1\n",
    "\n",
    "        while ans != 0:\n",
    "            re_val <<= 1\n",
    "            re_val += ans%2\n",
    "            \n",
    "            ans >>= 1\n",
    "        \n",
    "        return re_val << ones"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        return int(''.join(list(map(lambda b: ('1', '0')[b == '1'], bin(num)[2:]))), 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        highbit = 0\n",
    "        for i in range(1, 30 + 1):\n",
    "            if num >= (1 << i):\n",
    "                highbit = i\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        mask = (1 << (highbit + 1)) - 1\n",
    "        return num ^ mask"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        res = 1\n",
    "        while res <= num:\n",
    "            num = res ^ num\n",
    "            res <<= 1\n",
    "        \n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        n = num\n",
    "        for i in (1, 2, 4, 8, 17):\n",
    "            n |= n >> i\n",
    "        return n ^ num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        highbit = 0\n",
    "        for i in range(1, 30 + 1):\n",
    "            if num >= (1 << i):\n",
    "                highbit = i\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        mask = (1 << (highbit + 1)) - 1\n",
    "        return num ^ mask\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        i = ans = 0\n",
    "        while num:\n",
    "            if not num & 1:\n",
    "                ans += 1 << i\n",
    "            num >>= 1\n",
    "            i += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        highbit = 0\n",
    "        for i in range(1, 30 + 1):\n",
    "            if num >= (1 << i):\n",
    "                highbit = i\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        mask = (1 << (highbit + 1)) - 1\n",
    "        return num ^ mask\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/number-complement/solutions/1050060/shu-zi-de-bu-shu-by-leetcode-solution-xtn8/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        # 最简单的方式，只要找到这个数所在二进制区间中最大的数是谁就行，最大数是2**n-1\n",
    "        bitNum = 0\n",
    "        n = num\n",
    "        while (n):\n",
    "            n //= 2\n",
    "            bitNum += 1\n",
    "        print(bitNum)\n",
    "        return pow(2, bitNum) - 1 - num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        k = 1\n",
    "        while 2 ** k <= num: k += 1 \n",
    "        return num^ (2**k-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        def a(x):\n",
    "            if x == 0:\n",
    "                return 1\n",
    "            elif x == 1:\n",
    "                return 0\n",
    "        num = list(str(bin(num)))\n",
    "        \n",
    "        return int(\"\".join([str(a(int(i))) for i in num[2:]]),2)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        s = list(bin(num)[2:])\n",
    "        t = ['1' for i in range(len(s))]\n",
    "        for i in range(len(s)):\n",
    "            s[i] = str(int(s[i]) ^ int(t[i]))\n",
    "        s = int(''.join(s), 2)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        return num ^ ((1 << (len(bin(num)) - 2)) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        num_bin = bin(num)[2:]\n",
    "        change_list = ['0' if i =='1' else '1' for i in num_bin]\n",
    "        return int(''.join(change_list), 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        res = 0\n",
    "        stack = [] \n",
    "\n",
    "        while num > 0:\n",
    "            stack.append(1 - num%2)\n",
    "            num = num // 2  \n",
    "        \n",
    "        while stack:\n",
    "            res = res * 2 + stack.pop()\n",
    "        \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "\n",
    "        while num > 0:\n",
    "            if num%2 == 0:\n",
    "                ans += 1<<cur\n",
    "            cur += 1\n",
    "            num >>= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        highbit = 0\n",
    "        for i in range(1, 30 + 1):\n",
    "            if num >= (1 << i):\n",
    "                highbit = i\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        mask = (1 << (highbit + 1)) - 1\n",
    "        return num ^ mask\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        data = []\n",
    "        while num:\n",
    "            data.append(num & 1)\n",
    "            num >>= 1\n",
    "        data.reverse()\n",
    "        for i in range(len(data)):\n",
    "            if data[i] == 1:\n",
    "                data[i] = 0\n",
    "            else:\n",
    "                data[i] = 1\n",
    "        res = 0\n",
    "        while data:\n",
    "            if data.pop(0) == 1:\n",
    "                res += (2 ** (len(data)))\n",
    "        return res\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        highbit = 0\n",
    "        for i in range(1, 30 + 1):\n",
    "            if num >= (1 << i):\n",
    "                highbit = i\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        mask = (1 << (highbit + 1)) - 1\n",
    "        return num ^ mask\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        s=str(bin(num))\n",
    "        s=s[2::]\n",
    "        n=len(s)\n",
    "        z=''\n",
    "        a=0\n",
    "        for i in s:\n",
    "            if i=='1':\n",
    "                z=z+'0'\n",
    "            else:\n",
    "                z=z+'1'\n",
    "        for j in range(n):\n",
    "            a=int(z[j])*pow(2,n-1-j)+a\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        index = bin(num)[2:].find('0')\n",
    "\n",
    "        if index == -1:\n",
    "            return 0\n",
    "        return int('0b' + ''.join(['1' if b == '0' else '0' for b in bin(num)[index:]]), 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        tmp = bin(num)[2::]\n",
    "        tmp = (tmp)[::-1]\n",
    "        res = 0\n",
    "        weight = 2\n",
    "        for i in range(len(tmp)):\n",
    "            if tmp[i] == '0':\n",
    "                res += weight ** i\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        d = [0] * 32\n",
    "        res = 0\n",
    "        for i in range(32):\n",
    "            n = 1<<i\n",
    "            if n<num and not (n & num):\n",
    "                res+=n \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        a = []\n",
    "        ans = 0\n",
    "        while num>0:\n",
    "            a.append(num%2)\n",
    "            num //=2\n",
    "        for i in range(len(a)):\n",
    "            ans +=(1-a[i])*2**i\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        # 111 = 1000 - 1\n",
    "        ans, tmp = 1, num\n",
    "        while tmp:\n",
    "            tmp >>= 1\n",
    "            ans <<= 1\n",
    "\n",
    "        return ans - num - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        binary = str(bin(num))[2:]\n",
    "        bu = ''\n",
    "        for bit in binary:\n",
    "            if bit == '0':\n",
    "                bu = bu + '1'\n",
    "            else:\n",
    "                bu = bu + '0'\n",
    "\n",
    "        return int(bu,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        res=0\n",
    "        i=0\n",
    "        while(num!=1):\n",
    "            if num%2==0:\n",
    "                res+=2**i\n",
    "            num//=2\n",
    "            i+=1\n",
    "        return res\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        result, i = 0, 0\n",
    "        while num != 0:\n",
    "            if num % 2 == 0:\n",
    "                result += pow(2, i)\n",
    "            num //= 2\n",
    "            i += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        return pow(2,num.bit_length())-num-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        a = bin(num)\n",
    "        cur = '0b'\n",
    "        for i in a[2:]:\n",
    "            if i == '0':\n",
    "                cur += '1'\n",
    "            else:\n",
    "                cur += '0'\n",
    "        return int(cur,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        #return num ^ ((1 << (len(bin(num)) - 2)) - 1)\n",
    "        return num ^ ((1 << int(log(num, 2) + 1)) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        i = ans = 0\n",
    "        while num:\n",
    "            if not num & 1:\n",
    "                ans += 1 << i\n",
    "            num >>= 1\n",
    "            i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        t = 0\n",
    "        while num >= 2**t:\n",
    "            t += 1\n",
    "        return 2**t-1-num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        bn = bin(num)[2:]\n",
    "        bn = bn.replace('0', '!').replace('1', '0')\n",
    "        bn = bn.replace('!', '1')\n",
    "        c = int(bn, 2)\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        temp = \"\"\n",
    "        while (num != 0):\n",
    "            temp += str(num % 2)\n",
    "            num = num // 2\n",
    "        \n",
    "        newTemp = list(temp)\n",
    "        for i in range(len(newTemp)):\n",
    "            if newTemp[i] == \"1\":\n",
    "                newTemp[i] = 0\n",
    "            else:\n",
    "                newTemp[i] = 1\n",
    "\n",
    "        result = 0\n",
    "        for i in range(len(newTemp)):\n",
    "            result += newTemp[i] * (2 ** i)\n",
    "        \n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        bb=''\n",
    "        aa=list(\"{0:b}\".format(num))\n",
    "        for i in range(len(aa)):\n",
    "            if(aa[i]=='1'):\n",
    "               aa[i]='0'\n",
    "            else:\n",
    "               aa[i]='1'\n",
    "        for i in aa:\n",
    "              bb +=i\n",
    "        return int(bb,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        i = 1\n",
    "        while i <= num:\n",
    "            i *= 2\n",
    "        return i-1-num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        i = ans = 0\n",
    "        while num:\n",
    "            if not num & 1:\n",
    "                ans += 1 << i\n",
    "            num >>= 1\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        n=int(log(num,2))\n",
    "        return pow(2,n+1)-1-num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        ans = 0\n",
    "        cur = 0\n",
    "\n",
    "        while num > 0:\n",
    "            ans = ans + ((num%2==0)<<cur)\n",
    "            cur += 1\n",
    "            num >>= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        temp=1\n",
    "        while temp<num:\n",
    "            temp<<=1\n",
    "            temp|=1\n",
    "        # print(temp)\n",
    "        return temp^num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        ans=1\n",
    "        z=num\n",
    "        while num:\n",
    "            ans<<=1\n",
    "            num>>=1\n",
    "        return z^(ans-1)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        ans = 0\n",
    "        cur = 1\n",
    "        n = num\n",
    "        while n != 0:\n",
    "            if (n & 1):\n",
    "                ans = ans | 0\n",
    "            else:\n",
    "                ans = ans | cur\n",
    "            n = n >> 1\n",
    "            cur = cur << 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        return 2**(len(str(bin(num)))-2)-1-num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        bn = bin(num)[2:]\n",
    "        # bn = bn.replace('0', '!').replace('1', '0')\n",
    "        # bn = bn.replace('!', '1')\n",
    "        # c = int(bn, 2)\n",
    "        # return c\n",
    "        # 替换，或者1减去当前位的元素，或者用新串存入相反的元素\n",
    "        r = ''\n",
    "        # for i in bn:\n",
    "        #     if i == '1':\n",
    "        #         r += '0'\n",
    "        #     else:\n",
    "        #         r += '1'\n",
    "        # return int(r, 2)\n",
    "\n",
    "        for i, x in enumerate(bn):  #str类型不支持直接对某个元素赋值\n",
    "            r += str(1 - int(x))\n",
    "        return int(r, 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        s=''\n",
    "        num=bin(num)[2:]\n",
    "        for i in num:\n",
    "            if i=='1':\n",
    "                s+='0'\n",
    "            else:\n",
    "                s+='1'\n",
    "        return int(s,2)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        highbit = 0\n",
    "        for i in range(1, 31):\n",
    "            if num >= (1 << i):\n",
    "                highbit = i\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        mask = (1<<(highbit+1)) - 1\n",
    "        return num ^ mask"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        s = bin(num)[2:]\n",
    "        ans = 0\n",
    "        for c in s:\n",
    "            ans = 2 * ans + 1 if c == '0' else 2 * ans\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        x=num\n",
    "        digit=1\n",
    "        for i in range(31):\n",
    "            if x==0:\n",
    "                break\n",
    "            num^=digit\n",
    "            digit<<=1\n",
    "            x>>=1\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "\n",
    "        s = bin(num)[2:]\n",
    "        sss = ''\n",
    "\n",
    "        for i in s:\n",
    "            sss+=str(1 - int(i))\n",
    "\n",
    "\n",
    "        return int(sss,2) \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        ans = shift = 0\n",
    "        while num:\n",
    "            if not num & 1:\n",
    "                ans |= 1 << shift\n",
    "            shift += 1\n",
    "            num >>= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        count = 0\n",
    "        for i in str(bin(num)[2::]):\n",
    "            count += 1\n",
    "        newBit = ''\n",
    "        for i in bin(num)[2::]:\n",
    "            if i == '1':\n",
    "                newBit += \"0\"\n",
    "            else:\n",
    "                newBit += \"1\"\n",
    "        return int(\"0b\" + newBit, 2)\n",
    "       \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findComplement(self, num: int) -> int:\r\n",
    "        highbit = 0\r\n",
    "        for i in range(1, 30 + 1):\r\n",
    "            if num >= (1 << i):\r\n",
    "                highbit = i\r\n",
    "            else:\r\n",
    "                break\r\n",
    "        \r\n",
    "        mask = (1 << (highbit + 1)) - 1\r\n",
    "        return num ^ mask\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement0(self, num: int) -> int:\n",
    "        i = 1\n",
    "        while i <= num:\n",
    "            i *= 2\n",
    "        return i-1-num\n",
    "\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        ans = 0\n",
    "        p = 0\n",
    "        while num:\n",
    "            ans |= ((num  & 1) ^ 1) << p\n",
    "            num = num >> 1\n",
    "            p += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        count = 0\n",
    "        cur = num\n",
    "        while cur > 0:\n",
    "            count += 1\n",
    "            cur = cur // 2  \n",
    "        \n",
    "        return 2**count - 1 - num "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        return 2**len(bin(num)[2:])-1-num\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        str=bin(num)[2:]\n",
    "        result=''\n",
    "        for i in str:\n",
    "            result+='1' if i=='0' else '0'\n",
    "        return int(result,2)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        string = bin(num)[2:]\n",
    "        num_list = ['0']*len(string)\n",
    "        for i in range(len(string)):\n",
    "            if string[i] == '0':\n",
    "                num_list[i] = '1'\n",
    "            else:\n",
    "                num_list[i] = '0'\n",
    "        return int(''.join(num_list),2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        tmp = list(bin(num))\n",
    "        for i in range(2,len(tmp)):\n",
    "            if tmp[i] == '0':\n",
    "                tmp[i] = '1'\n",
    "            else:\n",
    "                tmp[i] = '0'\n",
    "        res = ''.join(tmp)\n",
    "        return int(res, 2)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        n = 2\n",
    "        while n - 1 < num:\n",
    "            n *= 2\n",
    "        return n - 1 - num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def findComplement(self, num):\n",
    "        # 将整数转换为二进制表示\n",
    "        binary = bin(num)[2:]\n",
    "        # 对二进制表示进行取反操作\n",
    "        complement = ''.join(['1' if b == '0' else '0' for b in binary])\n",
    "        # 将取反后的二进制表示转换为十进制表示\n",
    "        return int(complement, 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        num = str(bin(num))[2:]\n",
    "\n",
    "        list_num = []\n",
    "        for i in num:\n",
    "            list_num.append(int(i))\n",
    "        \n",
    "        print(list_num)\n",
    "\n",
    "        for i in range(len(list_num)):\n",
    "            print(\"list_num[%d] = %d\" %(i,list_num[i]))\n",
    "            if list_num[i] == 1:\n",
    "                list_num[i] = 0\n",
    "            elif list_num[i] == 0:\n",
    "                list_num[i] = 1\n",
    "        \n",
    "        \n",
    "        print(list_num)\n",
    "        string = \"\"\n",
    "        for i in list_num:\n",
    "            string += str(i)\n",
    "\n",
    "        print(string)\n",
    "            \n",
    "\n",
    "        return int(string,2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        return 2**len(bin(num)[2:])-1-num\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        i = ans = 0\n",
    "        while num:\n",
    "            if not num & 1:\n",
    "                ans += 1 << i\n",
    "            num >>= 1\n",
    "            i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        bn = bin(num)[2:]\n",
    "        # bn = bn.replace('0', '!').replace('1', '0')\n",
    "        # bn = bn.replace('!', '1')\n",
    "        # c = int(bn, 2)\n",
    "        # return c\n",
    "        # 替换，或者1减去当前位的元素，或者用新串存入相反的元素\n",
    "        r = ''\n",
    "        # for i in bn:\n",
    "        #     if i == '1':\n",
    "        #         r += '0'\n",
    "        #     else:\n",
    "        #         r += '1'\n",
    "        # return int(r, 2)\n",
    "\n",
    "        for i, x in enumerate(bn):\n",
    "            r += str(1 - int(x))\n",
    "        return int(r, 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        i = ans = 0\n",
    "        while num:\n",
    "            if not num & 1:\n",
    "                ans += 1 << i\n",
    "            num >>= 1\n",
    "            i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findComplement(self, num: int) -> int:\n",
    "        s=bin(num)[2:]\n",
    "        \n",
    "        arr=[str(int(x!=\"1\")) for x in s ]\n",
    "        #print(arr)\n",
    "        news=\"\".join(arr)\n",
    "        return int(news,2)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
